package com.wp.InterviewAlgorithm.lesson1;

/**
 * Created by 王萍 on 2017/8/26 0026.
 */

/**
 * 给定一个链表，翻转该链表从m到n的位置。
 * 要求直接翻转而非申请新的空间。
 * 如：给定1->2->3->4->5，m=2，n=4，返回1->4->3->2->5
 * 1<=m<=n<=链表长度
 */
public class 链表的部分翻转 {

    private static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(Integer.MAX_VALUE);//作为一个特定的起始节点。

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        printNode(head);
        Node result = partReverse(head, 3, 6);
        printNode(result);
    }

    /**
     * 1.以第start-1个节点为head，第start个节点为endNode，currentNode为endNode后的节点
     * 2.从currentNode开始遍历n-m次，遍历过程中将节点插入为head的next，即头插法。
     * 3.遍历完的currentNode为endNode的next。
     */
    public static Node partReverse(Node node, int start, int end) {

        if (node == null) return null;
        Node head = node;

        for (int i=0;i<start-1;i++){
            head = head.next;
        }

        Node endNode = head.next;
        Node currentNode = endNode.next;
        Node insertNode;
        for (int i = 0; i < end - start; i++) {
            insertNode = currentNode;
            currentNode = currentNode.next;
            insertNode.next = head.next;
            head.next = insertNode;
        }
        endNode.next = currentNode;
        return node;
    }

    public static void printNode(Node node) {
        StringBuilder builder = new StringBuilder("");
        node = node.next;//从第二个节点开始，第一个节点是一个特定的起始节点
        while (node != null) {
            builder.append(node.value).append("->");
            node = node.next;
        }
        System.out.println(builder.substring(0, builder.length() - 2));
    }
}
